#pragma once

#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
#include<thread> 
#include<mutex> //锁

using std::cout;
using std::endl;

//不同系统的页号大小的分配区间可能不同,假设一个页的大小是2^13
//32位页号最大值: 2^32/2^13 = 2^19
//64位页号最大值: 2^64/2^13 = 2^51

//_WIN64可兼容_WIN32的特性,要是先让_WIN32进行判断,一直都会进入_WIN32的条件里面
#ifdef _WIN64
	typedef size_t PAGE_ID;
#elif _WIN32
	typedef unsigned long long PAGE_ID;
#else
	//Linus
#endif


//ThreadCache能申请的最大数量
static const int Max_Size = 256 * 1024;
//哈希桶(自由链表)的数量
static const int NFREELIST = 208;

//返回obj位置所存储的引用,里面的内容指向下一个节点的地址
inline void*& NextObj(void* obj)
{
	return *(void**)obj;
}
class FreeList
{
public:
	bool Empty()
	{
		return _freelist == nullptr;
	}
	//头插
	void Push(void* obj)
	{
		assert(obj);

		NextObj(obj) = _freelist;
		_freelist = obj;
	}
	//头删
	void* Pop()
	{
		assert(_freelist);
		void* obj = _freelist;
		_freelist = NextObj(obj);
		return obj;
	}

private:
	void* _freelist = nullptr;
};

//计算对象大小的映射关系
class SizeClass
{
private:
	//传字节大小和对齐数
	static size_t _RoundUp(size_t bytes, int align)
	{
		return ((bytes + align - 1) & ~(align - 1));
	}

	//传字节大小和对齐数是2的几次方
	static int _Index(size_t bytes, int align_shift)
	{
		return ((bytes + (1<<align_shift) - 1) >> align_shift) - 1;
	}
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]                  8byte对齐        freelist[0,16)
	// [128+1,1024]             16byte对齐       freelist[16,72)
	// [1024+1,8*1024]          128byte对齐      freelist[72,128)
	// [8*1024+1,64*1024]       1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]     8*1024byte对齐   freelist[184,208)
	//对数字向上取整,用来构建哈希桶
	static size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	//计算映射哪一个哈希桶
	static size_t Index(size_t bytes)
	{
		assert(bytes <= Max_Size);

		//每个区间有多少个哈希桶
		static int group_array[4] = { 16,56,56,56 };

		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}
};

//------------CentralCache
//中心缓存哈希桶挂着的是一个个Span,Span下面再挂接着一个个切好的内存
//因为找OS分配到的资源是以页为单位的,不同内存大小的桶分配到的页数是不同的,一个Span可能有多个页,用完一个Span再申请一个
struct Span
{
	PAGE_ID _pageId = 0;	//大块内存起始页的页号
	size_t _n = 0;			//页数

	size_t _usecount = 0;	//切好的小块内存分配给ThreadCache的数量
	void* _freelist = nullptr;//切好的小块内存的自由链表

	Span* _prev = nullptr;	//双向
	Span* _next = nullptr;
};

//双向带头循环
class SpanList
{
public:
	SpanList()
	{
		_head = new Span();
		_head->_prev = _head;
		_head->_next = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);//不能删除头节点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
private:
	Span* _head;
};